package leetcode.L500;

public class EX5 {

    public String longestPalindrome(String s) {
        int len = s.length();
        int [][] dp = new int [len][len];
        String res = String.valueOf(s.charAt(0));
        for(int i = 0 ; i<len ;i++){
            dp[i][i] = 1;
        }
        for(int l = 2 ; l<=len ; l++){
            for (int i = 0; i <= len-l; i++) {
                int j = i + l -1;
                if(l==2 && s.charAt(i) == s.charAt(j)){
                    dp[i][j] = 1;
                }else if(dp[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)){
                    dp[i][j] = 1;
                }
                if(dp[i][j] == 1 && l > res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;

    }
//    public String longestPalindrome(String s) {
//        //动态规划思想，长度为1都是回文串，以此双边延展，如果双边相等且字串是回文串
//        int len = s.length();
//        int [][] dp = new int[len][len];
//        int res[] = new int[3];
//        res[0]=1;
//
//        for(int i = 0;i<len;i++){
//            dp[i][i]=1;
//        }
//        for(int l=2;l<=len;l++){
//            for(int i = 0;i<len-l;i++){
//                int j = i+l-1;
//                if(s.charAt(i)!=s.charAt(j)){
//                    dp[i][j] = 0;
//                }else{
//                    if(l==2||dp[i+1][j-1]==1){
//                        dp[i][j]=1;
//                    }else{
//                        dp[i][j]=0;
//                    }
//                }
//                if(dp[i][j]==1&&l>res[0]){
//                    res[0]=l;
//                    res[1]=i;
//                    res[2]=j;
//                }
//            }
//        }
//        return s.substring(res[1],res[2]+1);
//    }

    public static void main(String[] args) {
        EX5 ex5 = new EX5();
        ex5.longestPalindrome("bb");
    }
}
